Minkowski sum
The Minkowski sum of two sets of position vectors
Analogously, the Minkowski difference is defined as
Properties
For Minkowski addition, the zero set
The empty set is important in Minkowski addition, because the empty set annihilates every other subset: for every subset,
Minkowski addition behaves well with respect to the operation of taking convex hulls, as shown by the following proposition:
- For all non-empty subsets
and of a real vector-space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls
This result holds more generally for each finite collection of non-empty sets
If
Minkowski sums act linearly on the perimeter of two-dimensional convex bodies: the perimeter of the sum equals the sum of perimeters.
Algorithms for computing Minkowski sums
Planar case
Two convex polygons in the plane
For two convex polygons
Other
If one polygon is convex and another one is not, the complexity of their Minkowski sum is
Problems
- Minkowski Sums
- Kiddie Pool1
- Board game
- Fireworks2
- Bridge Building3
- Mogohu Ree Idol4
- TrianglePainting5
- Gears6
External links
- http://codeforces.com/blog/entry/18204?#comment-231204↩
- http://codeforces.com/blog/entry/44657?#comment-293094↩
- http://codeforces.com/blog/entry/17483?#comment-223283↩
- http://codeforces.com/blog/entry/2121?locale=en↩
- http://codeforces.com/blog/entry/18241?#comment-231500↩
- http://codeforces.com/blog/entry/15208↩